#include "Graph.h"
#include <queue>

//判断是否存在负环，以及存在负边时的最短路径搜索
void SPFA(Graph* g, int start)
{
    queue<GraphNode *> q;
    //用于标记节点是否在队中
    bool enter[g->nodeSet.size()] = {0};
    //记录到达一个节点的最短路径的边数，在不存在环的情况下，最多n-1，n为节点数
    int readCnt[g->nodeSet.size()] = {0};
    g->nodeSet[start]->weight = 0;
    q.push(g->nodeSet[start]);
    while (!q.empty())// 所有点的权重无法再减小时才会退出
    {
        auto cur = q.front();
        q.pop();
        enter[cur->value] = 0;
        for(auto e : cur->edges)
        {
            auto t = e->to;
            if(t->weight > cur->weight + e->weight)
            {
                t->weight = cur->weight + e->weight;
                readCnt[t->value] = readCnt[cur->value] + 1;
                // if(readCnt[t->value] >= n)
                // {
                //     printf("YES\n");//存在负环
                //     return;
                // }
                if(!enter[t->value])
                {
                    q.push(t);
                    enter[t->value] = 1;
                }
            }
        }
    }
    //printf("NO\n");//不存在负环
}